package com.sourcetrip.raw.adt;


import com.sourcetrip.raw.adt.interfaces.MyLinkedListInterfaces;

/**
 * @author: ZhouBert
 * @date: 2020/11/17
 * @description: 我的单链表 知识点的承接：
 * -关于 【动态数组集合（ArrayList）】的思考：
 * 优点：查询快；【数组的优点在于有索引，查找 O(1)】
 * 缺点：
 * 1.增删慢（数组属性带来的）；（消耗CPU 性能）
 * 2.浪费内存空间：需要连续的内存空间 + 每一次扩容 1.5 倍，可能有大量空间用不上；
 * -- 那么，他来了 linkedList
 * 【单链表，双链表，循环链表】
 * 定义：由链将一个个元素（Node）连接，每一个元素我们通常称之为 Node 节点；
 * Node 节点：本身的值(value)以及指向下一个节点(next:Node)，类似方法区指向堆区；
 * linkedList 拥有第一个 node 的内存地址。
 * 链表的删除 O(1)：
 * 我认为虽然有查找的前提，但是不应该被计入损耗。因为实际中，都是先确定了要删除的元素，再进行删除，此时毫无疑问是 O(1) 的；
 * -------
 * 接下来是我自己实现的单链表
 * -------
 * 优化：
 * 1.从整体上看，核心应该是 get() ,关键方法是 add(),remove() 但是，这两个都是基于 get() 的思路！
 * 因为在 链表中，并没有随机访问的能力，只能通过自己写的 get() 去定位方法！
 * 2.在 clear() 方法中，应该考虑 可达性算法！有关 GC 回收
 * 3.在 indexOf() 中，必须区分 null 与 equals ，虽然equals 没错，但是对于 null 的判断是只能用 == 的，于是只能分开判断！
 * 4.有个bug,add(index,element) 中 index 是可以等于 size 的，所以应该有两套 index 的判断方法！
 */
public class MySingleLinkedList<E> implements MyLinkedListInterfaces<E> {

	private int size = 0;

	/**
	 * 哨兵节点
	 */
	MySingleNode<E> guard = new MySingleNode<>(null, null);

	/**
	 * 指针节点
	 */
	MySingleNode<E> cur = guard;


	@Override
	public int size() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	/**
	 * 判断单链表中是否存在该元素
	 * 单链表的遍历还是有点绕的！
	 *
	 * @param element
	 * @return
	 */
	@Override
	public boolean contains(E element) {
		if (isEmpty()) {
			return false;
		}
		//从哨兵节点开始遍历
		MySingleNode<E> point = this.guard;
		while (point.getNext() != null) {
			MySingleNode next = point.getNext();
			// 如果内容相同（反正默认会比较内存地址）
			if (next.getElement().equals(element)) {
				return true;
			}
			point = next.getNext();
		}
		return false;
	}

	/**
	 * 将元素添加到尾节点
	 *
	 * @param element
	 */
	@Override
	public void add(E element) {
		//如果是空节点
		if (isEmpty()) {
			guard.setNext(new MySingleNode(element, null));
			//将当前节点指向尾节点的引用
			cur = guard.getNext();
		} else {
			//此时应该已经完成 cur 执行尾节点
			// 创建一个临时节点
			MySingleNode<E> tempNode = this.cur;
			this.cur.setNext(new MySingleNode(element, null));
			cur = tempNode.getNext();
		}
		size++;
	}

	/**
	 * 将元素添加到索引指定个位置
	 *
	 * @param index	此时 index 是可以 == size 的
	 * @param element
	 */
	@Override
	public void add(int index, E element) {
		check4Index(index);
		MySingleNode<E> point = this.guard;
		//前一个节点
		MySingleNode<E> pre = null;
		//index 的前一个索引值
		int i = -1;
		while (i < index) {
			//最终指向的是引用
			pre = point;
			point = point.getNext();
			i++;
		}

		//此时 i == index
		pre.setNext(new MySingleNode(element, point));
		size++;
	}

	/**
	 * 获取索引位置的 元素
	 *
	 * @param index
	 * @return
	 */
	@Override
	public E get(int index) {
		check4Index(index);
		MySingleNode<E> point = this.guard;
		//前一个节点
		MySingleNode<E> pre = null;
		int i = -1;
		while (i < index) {
			//最终指向的是引用
			pre = point;
			point = point.getNext();
			i++;
		}
		return point.getElement();
	}

	/**
	 * 设置 索引位置的 元素
	 *
	 * @param index
	 * @param element
	 * @return
	 */
	@Override
	public E set(int index, E element) {
		check4Index(index);
		MySingleNode<E> point = this.guard;
		//前一个节点
		MySingleNode<E> pre = null;
		int i = -1;
		while (i < index) {
			//最终指向的是引用
			pre = point;
			point = point.getNext();
			i++;
		}
		E oldValue = point.getElement();
		point.setElement(element);
		return oldValue;
	}

	/**
	 * 移除对应索引位置的 元素
	 * @param index
	 * @return
	 */
	@Override
	public E remove(int index) {
		check4Index(index);
		MySingleNode<E> point = this.guard;
		//前一个节点
		MySingleNode<E> pre = null;
		int i = -1;
		while (i < index) {
			//最终指向的是引用
			pre = point;
			point = point.getNext();
			i++;
		}
		E oldValue = point.getElement();
		pre.setNext(point.getNext());
		size--;
		return oldValue;
	}

	@Override
	public int indexOf(E element) {
		MySingleNode<E> point = this.guard;
		int i = -1;
		while (point.getNext()!=null) {
			//最终指向的是引用
			point = point.getNext();
			i++;
			if (point.getElement().equals(element)) {
				return i;
			}
		}
		return -1;
	}

	@Override
	public void clear() {
		//处理哨兵节点的指向
		guard.setNext(null);
		//将当前节点指向哨兵
		cur = guard;
		//将大小值为 0
		size = 0;
	}

	@Override
	public String toString() {
		MySingleNode<E> pre = this.guard;
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		while (pre.getNext() != null) {
			MySingleNode temp = pre.getNext();
			sb.append(temp.getElement()).append(", ");
			pre = pre.getNext();
		}
		sb.append("]");
		return sb.toString();
	}

	//region	private methods

	/**
	 * 检验 index
	 *
	 * @param index
	 */
	private void check4Index(int index) {
		if (index >= size) {
			throw new RuntimeException("index 超出界限！");
		}
	}

	//endregion
}
